#include "staticLinkedList.h"

int allocNode(StaticList *list) {
    // 从备用空间取一个结点
    int newNodeAddr = list[SPARE]->link;

    if (list[SPARE]->link != 0) {
        list[SPARE]->link = list[newNodeAddr]->link;
    }

    return newNodeAddr;
}

void freeNode(StaticList *list, int freeNodeAddr) {
    list[freeNodeAddr]->link = list[SPARE]->link;
    list[SPARE]->link = list[freeNodeAddr]->link;
}

void initSList(StaticList *list) {
    for (int i = SPARE; i < MAX_SIZE-1; ++i) {
        list[i]->link = i+1;
    }
    list[MAX_SIZE-1]->link = 0;
    list[HEAD]->link = -1;
}

void displaySList(StaticList *list) {
    if (list[HEAD]->link == -1) {
        printf("Empty list.\n");
        return;
    }

    int i = list[HEAD]->link;
    while (i != -1) {
        printf("%c -- ", list[i]->data);
        i = list[i]->link;   // 相当于 p = p->link

        // 为美观, 最后一个结点单独输出
        if (list[i]->link == -1) {
            printf("%c.\n", list[i]->data);
            break;
        }
    }
}

// 首插法
void instertNodeAtBeginning(StaticList *list, DataType insertData) {
    int newNodeAddr = allocNode(list);
    if (newNodeAddr == 0) {
        printf("Failed. Because the list is full.\n");
        return;
    }

    list[newNodeAddr]->data = insertData;
    if (list[HEAD]->link == -1) {
        // 第一个被插入的结点即作为最后结束的结点
        list[newNodeAddr]->link = -1;
    } else {
        // 新插入结点的后继为原首元结点
        list[newNodeAddr]->link = list[HEAD]->link;
    }
    // 新插入的结点作为新的首元结点
    list[HEAD]->link = newNodeAddr;
}

// 首删法
void deleteNodeAtBeginning(StaticList *list) {
    int delNodeAddr = list[HEAD]->link;
    list[HEAD]->link = list[delNodeAddr]->link;

    // 将被删除的结点插在备份空间的第一个
    // list[delNodeAddr]->link = list[SPARE]->link;
    // list[SPARE]->link = delNodeAddr;

    // 把上面注释的内容交给 freeNode() 函数来完成
    freeNode(list, delNodeAddr);
}